#ifndef __BLINKLIST_HPP_
#define __BLINKLIST_HPP_

#include <iostream>
template<typename T>
class BLinkTree
{
public:
    BLinkTree();
    ~BLinkTree();

    /* 调用插入函数 */
    void Insert(const T & element);
    /* 调用删除函数 */
    void Remove(const T & element);
    /* 调用查找函数 */
    T * FindNode(const T & element);
    /* 输出函数 */
    void show();

private:
    struct Node
    {
        Node(T element)
        {
            data = element;
            left = right = parent = nullptr;
        }
        T data;
        Node *left;     //左孩子
        Node *right;    //右孩子
        Node *parent;   //双亲节点
    };
    /* 插入节点 */
    Node * InsertNode(Node * node,const T & element);
    /* 删除节点 */
    Node * RemoveNode(Node * node,const T & element);
    /* 找到最小的节点 */
    Node * GetMinNode(Node * node);
    /* 查找函数 */
    T * FindNode(Node * node,const T & element);

    /* 前序遍历 */
    void PrevTravel(Node * node);
    /* 中序遍历 */
    void MidTravel(Node * node);
    /* 后序遍历 */
    void PostTravel(Node * node);

    /* 求高度 */
    int GetNodeHeight(Node * node);
    /* 判断是否平衡 */
    int LeftRightDeviation(Node * node);

    /* ………………失衡旋转……………… */
    /* 左旋 */
    Node * RotateLeft(Node * node);
    /* 右旋 */
    Node * RotateRight(Node * node);
    /* 左右旋 */
    Node * RotateLeftRight(Node * node);
    /* 右左旋 */
    Node * RotateRightLeft(Node * node);
    
    Node * root;//成员变量

};

template <typename T>
BLinkTree<T>::BLinkTree()
{
    root = nullptr;
}

template <typename T>
BLinkTree<T>::~BLinkTree()
{
}

template <typename T>
void BLinkTree<T>::Insert(const T &element)
{
    root = InsertNode(root,element);
}

template <typename T>
void BLinkTree<T>::Remove(const T &element)
{
    root = RemoveNode(root,element);
}

template <typename T>
T *BLinkTree<T>::FindNode(const T &element)
{
    return FindNode(root,element);
}

template <typename T>
inline void BLinkTree<T>::show()
{
    PrevTravel(root);
    std::cout<<std::endl;
    MidTravel(root);
    std::cout<<std::endl;
    PostTravel(root);
    std::cout<<std::endl;
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::InsertNode(Node *node, const T &element)
{
    //如果没有节点为空，则创建节点
    if(node == nullptr)    
        return new Node(element);   //创建节点  //插入1的时候直接创建一个头节点
    //节点的值等于element，也不插入
    if(node->data == element)
        return node;
    //插入到左子树
    if(element < node->data)
    {
        //递归插入
        node->left = InsertNode(node->left,element);
        //失衡-左子树重
        if(LeftRightDeviation(node) > 1)
        {
            //左左失衡
            if(element < node->left->data)
            {
                node = RotateRight(node);
            }
            //左右失衡
            else
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right = InsertNode(node->right,element);
        if(LeftRightDeviation(node) < -1)
        {
            //右左失衡
            if(element < node->right->data)
            {
                node = RotateRightLeft(node);
            }
            //右右失衡
            else
            {
                node = RotateLeft(node);
            }
        }
    }
    return node;
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::RemoveNode(Node *node, const T &element)
{
    if(node == nullptr)
        return node;
    if(element < node->data)
    {
        node->left = RemoveNode(node->left,element);
    }
    else if(element > node->data)
    {
        node->right = RemoveNode(node->right,element);
    }
    else
    {
        //只有一个孩子或左右都没有孩子
        if(node->left == nullptr || node->right == nullptr)
        {
            Node * temp = node->left ? node->left : node->right;
            //叶子，删除叶子
            if(temp == nullptr)
            {
                delete node;
                node = nullptr;//不能return nullptr
            }
            else
            {
                temp->parent = node->parent;
                delete node;
                node = temp;
            }
        }
        //有两个孩子
        else//重新听一下
        {
            Node * min = GetMinNode(node->right);
            node->data = min->data;
            node->right = RemoveNode(node->right,min->data);
        }
    }

    if(node == nullptr)
        return node;
    //左子树重
    if(LeftRightDeviation(node) > 1)
    {
        //左子树的左边更重 左左
        if(LeftRightDeviation(node->left) > 0)  //为什么大于0
        {
            node = RotateRight(node);
        }
        //左右
        else
        {
            node = RotateLeftRight(node);
        }
    }
    else if(LeftRightDeviation(node) < -1)
    {
        //右左
        if(LeftRightDeviation(node->right) > 0)
        {
            node = RotateRightLeft(node);
        }
        //右右
        else
        {
            node = RotateLeft(node);
        }
    }
    return node;//经过以上操作，返回node
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::GetMinNode(Node *node)
{
    Node * min = node;
    while(min->left != nullptr)
    {
        min = min->left;
    }
    return min;
}

template <typename T>
T *BLinkTree<T>::FindNode(Node *node, const T &element)
{
    if(node == nullptr)
        return nullptr;
    if(node->data == element)
        return & node->data;
    else if(node->data > element)
    {
        return FindNode(node->left,element);
    }
    else
    {
        return FindNode(node->right,element);
    }
}

template <typename T>
void BLinkTree<T>::PrevTravel(Node *node)
{
    if(node == nullptr)
        return;
    std::cout<<node->data<<" "; //中
    //showPtr(node->data);
    PrevTravel(node->left);     //左
    PrevTravel(node->right);    //右
}

template <typename T>
void BLinkTree<T>::MidTravel(Node *node)
{
    if(node == nullptr)
        return;
    MidTravel(node->left);     //左
    std::cout<<node->data<<" "; //中
    //showPtr(node->data);
    MidTravel(node->right);    //右
}

template <typename T>
void BLinkTree<T>::PostTravel(Node *node)
{
    if(node == nullptr)
        return;
    PostTravel(node->left);     //左
    PostTravel(node->right);    //右
    std::cout<<node->data<<" "; //中
    //showPtr(node->data);
}

template <typename T>
int BLinkTree<T>::GetNodeHeight(Node *node)
{
    if(node == nullptr)
        return 0;
    int lh = GetNodeHeight(node->left);//二叉树只需要考虑两个孩子
    int rh = GetNodeHeight(node->right);
    return (lh > rh ? lh : rh) + 1;
}

template <typename T>
int BLinkTree<T>::LeftRightDeviation(Node *node)
{
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::RotateLeft(Node *node)
{
    Node * t = node->right;
    node->right = t->left;
    t->left = node;

    t->parent = node->parent;
    node->parent = t;
    return t;
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::RotateRight(Node *node)
{
    Node * t = node->left;
    node->left = t->right;
    t->right = node;//

    t->parent = node->parent;
    node->parent = t;
    return t;
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::RotateLeftRight(Node *node)
{
    //先把左子树左旋
    node->left = RotateLeft(node->left);
    //再进行右旋，返回新的根
    return RotateRight(node);
}

template <typename T>
typename BLinkTree<T>::Node *BLinkTree<T>::RotateRightLeft(Node *node)
{
    //先把右子树右旋
    node->right = RotateRight(node->right);
    //再进行右旋，返回新的根
    return RotateLeft(node);
}

#endif